#include <iostream>

using namespace std;

// 236. 二叉树的最近公共祖先
// 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        this->p = p;
        this->q = q;
        dfs(root);
        return ans;
    }

private:
    TreeNode* p;
    TreeNode* q;
    TreeNode* ans;
    pair<bool ,bool> dfs(TreeNode* root) {
        if(root == nullptr) return {false, false};
        pair<bool, bool> leftResult = dfs(root->left);
        pair<bool, bool> rightResult = dfs(root->right);
        pair<bool, bool> result;
        result.first = leftResult.first || rightResult.first || root->val == p->val;
        result.second = leftResult.second || rightResult.second || root->val == q->val;
        if(result.first && result.second && ans == nullptr)
            ans = root;
        return result;
    }
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
